package com.atguigu.tree;

public class ArrBinaryTreeDemo {

  /*
  演示如何用数组来保存二叉树, 一般用于完全二叉树（要不然浪费）
  树->数组，根据层序遍历，将节点依次放入数组（完全二叉）

  特性：对应节点arr[i],其左孩子为 2i + 1, 右孩子 2i + 2
   */

  public static void main(String[] args) {
    int[] arr = {1, 2, 3, 4, 5, 6, 7};
    // 创建一个 ArrBinaryTree
    ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr);
    arrBinaryTree.preOrder(); // 1,2,4,5,3,6,7
  }
}

class ArrBinaryTree {
  private int[] arr; // 存储数据结点的数组

  public ArrBinaryTree(int[] arr) {
    this.arr = arr;
  }

  // 重载preOrder
  public void preOrder() {
    this.preOrder(0);
  }

  // 编写一个方法，完成顺序存储二叉树的前序遍历
  /**
   * @param index 数组的下标
   */
  public void preOrder(int index) {
    // 如果数组为空，或者 arr.length = 0
    if (arr == null || arr.length == 0) {
      System.out.println("数组为空，不能按照二叉树的前序遍历");
    }
    // 输出当前这个元素
    System.out.println(arr[index]);
    // 向左递归遍历
    if ((index * 2 + 1) < arr.length) {
      preOrder(2 * index + 1);
    }
    // 向右递归遍历
    if ((index * 2 + 2) < arr.length) {
      preOrder(2 * index + 2);
    }
  }
}
